package dfs.review;

import java.util.List;

public class Demo {

    /**
     * 合并两个有序链表
     * @param l1
     * @param l2
     * @return
     */
//    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//        if (l1 == null) return l2;
//        if (l2 == null) return l1;
//        if (l1.val < l2.val) {
//            l1.next = mergeTwoLists(l1.next, l2);
//            return l1;
//        } else {
//            l2.next = mergeTwoLists(l2.next, l1);
//            return l2;
//        }
//    }



    /**
     * 汉诺塔问题
     * @param a
     * @param b
     * @param c
     */
    public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {
        dfs(a,b,c,a.size());
    }

    public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
        if (n == 1) {
            c.add(a.remove(a.size() - 1));
            return;
        }
        dfs (a, c, b, n - 1);
        c.add(a.remove(a.size() - 1));
        dfs (b, a, c, n - 1);
    }
}
